Graphe distance-transitif

Familles de graphes définies par leurs automorphismes
distance-transitif	→	distance-régulier	←	fortement régulier
↓
symétrique (arc-transitif)	←	t-transitif, $(t \geq 2)$		symétrique gauche (en)
↓
_{(si connexe)} sommet-transitif et arête-transitif	→	régulier et arête-transitif	→	arête-transitif
↓		↓		↓
sommet-transitif	→	régulier	→	_{(si biparti)} birégulier
↑
graphe de Cayley	←	zéro-symétrique		asymétrique

Graphe de Biggs-Smith, le plus grand graphe cubique distance-transitif.

En théorie des graphes, un graphe non-orienté est distance-transitif si pour tous sommets u, v, x, y tels que u et v d'une part et x et y d'autre part sont à même distance, il existe un automorphisme de graphe envoyant u sur x et v sur y^[1]. Autrement dit, un graphe est distance-transitif si son groupe d'automorphisme agit transitivement sur chacun des ensembles de paires de sommets à même distance^[2].

↑ (en) Norman Biggs, Algebraic Graph Theory, 2^d Edition, Cambridge University Press, 1993, 214 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 155
↑ (en) Hajime Tanaka, Jack H. Koolen et Edwin R. van Dam, « Distance-regular graphs », The Electronic Journal of Combinatorics,‎ 23 octobre 2014, p. 20-21 (arXiv 1410.6294, lire en ligne, consulté le 2 juillet 2019)

[:0-1] (en) Norman Biggs, Algebraic Graph Theory, 2^d Edition, Cambridge University Press, 1993, 214 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 155

[:2-2] (en) Hajime Tanaka, Jack H. Koolen et Edwin R. van Dam, « Distance-regular graphs », The Electronic Journal of Combinatorics,‎ 23 octobre 2014, p. 20-21 (arXiv 1410.6294, lire en ligne, consulté le 2 juillet 2019)

[1]

[2]